package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-25 17:36
 */
public class BC213打家劫舍II {

    public static void main(String[] args) {
        int[] nums = {1, 1, 3, 6, 7, 10, 7, 1, 8, 5, 9, 1, 4, 4, 3};
        System.out.println(rob(nums));
    }

    /**
     * 需要记录打家劫舍的路径 是否包含1
     * 怎么判断是否包含1
     * 只要有连续两次不包含1 后面就不会再包含1了 同理如果两次都包含1 则后面都包含1
     *
     * 此方法有漏洞 如果最大的包含1 第二大的不包含1  但是第二大的加上最后一个数比最大的大 这种情况就没法利用最大路径了
     * <p>
     * 暴力点 直接把所有路径全部存着    XXX
     *
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length + 1];
        boolean[] dpFlag = new boolean[nums.length + 1];
        dp[0] = 0;
        dpFlag[0] = false;
        dp[1] = nums[0];
        dpFlag[1] = true;
        dp[2] = Math.max(nums[0], nums[1]);
        if (nums[1] >= nums[0]) {
            dpFlag[2] = false;
        } else {
            dpFlag[2] = true;
        }
        for (int i = 3; i <= nums.length; i++) {
            if (i == nums.length) {
                dp[i] = Math.max(dpFlag[i - 2] ? Math.max(dp[i - 2], nums[i - 1]) : dp[i - 2] + nums[i - 1],
                        dpFlag[i - 3] ? dp[i - 3] + nums[i - 2] : dp[i - 3] + Math.max(nums[i - 1], nums[i - 2]));
            } else {
                if (dp[i - 2] + nums[i - 1] > dp[i - 3] + Math.max(nums[i - 1], nums[i - 2])) {
                    //说明选择的是dp[i-2]
                    dpFlag[i] = dpFlag[i - 2];
                } else if (dp[i - 2] + nums[i - 1] == dp[i - 3] + Math.max(nums[i - 1], nums[i - 2])) {
                    dpFlag[i] = dpFlag[i - 2] && dpFlag[i - 3];
                } else {
                    dpFlag[i] = dpFlag[i - 3];
                }
                dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 3] + Math.max(nums[i - 1], nums[i - 2]));
            }
        }
        return dp[nums.length];
    }
}
